package one.three.thirtyEight;

public class GeneralizedQueue<Item> {
	private Item[] a;
	private int h;
	private int t;
	private int n;
	private static int initialSize = 4;

	public boolean isEmpty() {
		return n == 0;
	}

	public int size() {
		return n;
	}

	private void resize(int s) {
		Item[] temp = (Item[]) new Object[s];
		if (s > a.length) {
			if (h <= t) {
				for (int i = 0; i < a.length; i++) {
					temp[i] = a[i];
				}
			} else {
				for (int i = h; i < a.length; i++) {
					temp[i - h] = a[i];
				}
				for (int i = 0; i <= t; i++) {
					temp[i + a.length - h] = a[i];
				}
				h = 0;
				t = n - 1;
			}
		} else {
			if (h <= t) {

				for (int i = h; i <= t; i++) {
					temp[i - h] = a[i];
				}
				h = 0;
				t = n - 1;
			} else {
				for (int i = h; i < a.length; i++) {
					temp[i - h] = a[i];
				}
				for (int i = 0; i <= t; i++) {
					temp[i + a.length - h] = a[i];
				}
				h = 0;
				t = n - 1;
			}

		}
		a = temp;
	}

	public Item delete(int k) {
		Item r = null;
		if (k == 1) {
			r = dequeue();
		} else if (k <= n) {
			if (h <= t) {
				int idx = t - (k - 1);
				r = a[idx];
				for (int i = idx; i < t; i++) {
					a[i] = a[i + 1];
				}
				t--;
			} else {
				Item[] tmp = (Item[]) new Object[n];
				for (int i = h; i < a.length; i++) {
					tmp[i - h] = a[i];
				}
				for (int i = 0; i <= t; i++) {
					tmp[a.length - h + i] = a[i];
				}
				t = a.length - h + t;
				h = 0;
				int idx = t - (k - 1);
			
				a = tmp;
				r = a[idx];
				for (int i = idx; i < t; i++) {
					a[i] = a[i + 1];
				}
				t--;
			}
		}
		return r;
	}

	public void enqueue(Item item) {
		pushHead(item);
	}

	public void pushHead(Item item) {
		if (a == null) {
			a = (Item[]) new Object[initialSize];
			a[0] = item;
			n++;
			h = 0;
			t = 0;
		} else {
			int newH = h - 1;
			if (newH < 0) {
				newH += a.length;
			}
			a[newH] = item;
			h = newH;
			n++;
			if (n > a.length / 2) {
				resize(a.length * 2);
			}
		}
	}

	public void pushTail(Item item) {
		if (a == null) {
			a = (Item[]) new Object[initialSize];
			a[0] = item;
			n++;
			h = 0;
			t = 0;
		} else {
			int newT = t + 1;
			if (newT >= a.length)
				newT -= a.length;
			a[newT] = item;
			t = newT;
			n++;
			if (n > a.length / 2)
				resize(a.length * 2);
		}
	}

	public Item popHead() {
		if (a != null) {
			Item item = a[h];
			h++;
			if (h >= a.length) {
				h -= a.length;
			}
			n--;
			if (n < a.length / 4 && n > initialSize)
				resize(a.length / 2);

			return item;
		} else {
			return null;
		}
	}

	public Item popTail() {
		if (a != null) {
			Item item = a[t];
			t--;
			if (t < 0) {
				t += a.length;
			}
			n--;
			if (n < a.length / 4 && n > initialSize) {
				resize(a.length / 2);
			}
			return item;
		} else {
			return null;
		}
	}

	public Item dequeue() {
		Item r = popTail();
		return r;
	}

	@Override
	public String toString() {
		StringBuilder s = new StringBuilder();
		if (a != null) {
			if (h <= t) {
				for (int i = h; i <= t; i++) {
					s.append("[" + a[i] + "]");
				}
			} else {
				for (int i = h; i < a.length; i++) {
					s.append("[" + a[i] + "]");
				}
				for (int i = 0; i <= t; i++) {
					s.append("[" + a[i] + "]");
				}
			}
		}
		return s.toString();
	}

	public void showA() {
		for (int i = 0; i < a.length; i++) {
			System.out.println(a[i]);
		}
	}

	public static void main(String[] args) {
		GeneralizedQueue<Integer> q = new GeneralizedQueue<Integer>();
		for (int i = 0; i < 7; i++) {
			q.enqueue(i);
		}
		System.out.println(q);
		int r = q.delete(2);
		System.out.println(r);
		System.out.println(q);
	}

}
